﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.Hash
{
    //======================== HashMap
    //使用数组和set来做哈希法的局限
    //1)数组大小是受限的，而且如果元素很少，而哈希值太大会造成内存空间的浪费
    //2)set是一个集合，里面放的元素只能是一个key，而不是键值对。
    //map是一种key-value的存储结构。
    class SumOfNums
    {
        // =========================力扣001 两数之和
        //给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标
        //可假设每种输入只会对应一个答案，但数组中同一个元素只能使用一遍。
        public int[] TwoSum(int[] nums, int target)
        {
            int[] res = new int[2];
            if ( nums.Length == 0)
                return res;
            Hashtable hashtable = new Hashtable();
            for(int i = 0;i < nums.Length;i++)
            {
                int temp = target - nums[i];
                if(hashtable.Contains(temp))
                {
                    res[1] = i;
                    res[0] = (int)hashtable[temp];
                }
                hashtable[nums[i]] = i;
                //hashtable.Add(nums[i], i);
            }
            return res;
        }

        //============================ 力扣454 四数之和
        //给定四个包含整数的数组列表A,B,C,D,计算有多少个元素(i,j,k,l)，使得A[i] + B[j] + C[k] + D[l] = 0
        //为了使问题简单化，所有的A,B,C,D具有相同的长度N，且0<=N<=500.
        //所有整数的范围在（-2^28~2^28-1）之间，最终结果不会超过(2^31-1)。
        public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4)
        {
            Hashtable hashtable = new Hashtable();
            int count = 0;
            //遍历A数组和B数组，统计两个数组元素之和，和出现的次数，放到map中
            foreach (int a in nums1)
            {
                foreach (int b in nums2)
                {
                    if (hashtable.ContainsKey(a + b))
                    {
                        count = (int)hashtable[a + b];
                        hashtable[a + b] = ++count;
                    }
                    else
                    {
                        hashtable[a + b] = 1;
                    }
                }
            }
            //统计a+b+c+d=0出现的 次数
            count = 0;
            //遍历C数组和D数组。如果0-(c+d)在map中出现的话 ，记录key对应的value出现的次数
            foreach (int c in nums3)
            {
                foreach (int d in nums4)
                {
                    if (hashtable.ContainsKey(0 - (c + d)))
                    {
                        count += (int)hashtable[0 - (c + d)];
                    }
                }
            }
            return count;
        }

        //=======================力扣018 四数之和
        //给定一个由n个整数组成的数组nums，和一个目标值target。
        //请找出并返回满足夏素全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]]
        //0 <= a, b, c, d < n
        //a, b, c, d各不相同
        //nums[a] + nums[b] + nums[c] + nums[d] == target;
        public IList<IList<int>> FourSum(int[] nums, int target)
        {
            IList<IList<int>> result = new List<IList<int>>();
            Array.Sort(nums);
            for (int k = 0; k < nums.Length; k++)
            {
                //去重
                if (k > 0 && nums[k] == nums[k - 1])
                    continue;

                for(int i = k + 1; i<nums.Length;i++)
                {
                    //去重
                    if (i > k + 1 && nums[i] == nums[i - 1])
                        continue;
                    int left = i + 1;
                    int right = nums.Length - 1;
                    while(right > left)
                    {
                        if (nums[k] + nums[i] + nums[left] + nums[right] > target)
                            right--;
                        else if (nums[k] + nums[i] + nums[left] + nums[right] < target)
                            left++;
                        else
                        {
                            result.Add(new List<int>() { nums[k], nums[i], nums[left], nums[right] });
                            //去重逻辑放在找到第一个四元组之后
                            while (right > left && nums[right] == nums[right - 1])
                                right--;
                            while (right > left && nums[left] == nums[left + 1])
                                left++;
                            //找到答案时，双指针同时收缩
                            right--;
                            left++;
                        }
                    }
                }
            }
            return result;

        }

        //=======================力扣015 三数之和
        //给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a,b,c，使得a+b+c=0
        //找出所有和为0且不重复的三元组
        //注意[0， 0， 0， 0] 这组数据
        public IList<IList<int>> ThreeSum(int[] nums)
        {//哈希解法：两层for循环可以确定a和b的数值，然后可以使用哈希法确定0-(a+b)是否存在，但是需要去重的时候比较复杂
            IList<IList<int>> result = new List<IList<int>>();

            Array.Sort(nums);
            for(int i = 0;i<nums.Length;i++)
            {
                //排序之后如果a已经大于0，则不可能凑成三元组
                if (nums[i] > 0)
                    continue;
                //三元组元素a去重
                if (i > 0 && nums[i] == nums[i - 1])
                    continue;
                HashSet<int> set = new HashSet<int>();
                for(int j = i+1;j<nums.Length;j++)
                {
                    //三元组元素b去重
                    if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2])
                        continue;

                    int c = 0 - (nums[i] + nums[j]);
                    if(set.Contains(c))
                    {
                        result.Add(new List<int>() { nums[i], nums[j], c });
                        set.Remove(c);//三元组元素c去重
                    }
                    else
                    {
                        set.Add(nums[j]);
                    }
                }
            }
            return result;
        }
        public IList<IList<int>> ThreeSum_2(int[] nums)
        {//双指针法：
            IList<IList<int>> result = new List<IList<int>>();
            Array.Sort(nums);
            //a = nums[i],b=nums[left],c=nums[right]
            for(int i = 0;i<nums.Length;i++)
            {
                //排序之后如果a已经大于0，则不可能凑成三元组
                if (nums[i] > 0)
                    return result;

                //if(nums[i]==nums[i+1]) 错误去重方法，会漏掉 -1 -1 2
                if (i > 0 && nums[i] == nums[i - 1])//正确去重方法
                    continue;
                int left = i + 1;
                int right = nums.Length - 1;
                while (right > left)
                {
                    //去重复逻辑如果放这里的话，0，0，0的情况,可能直接导致right<=left,从而漏掉0,0,0
                    /*
                    while (right > left && nums[right] == nums[right - 1])
                        right--;
                    while (right > left && nums[left] == nums[left + 1])
                        left++;
                     */

                    if (nums[i] + nums[left] + nums[right] > 0)
                        right--;
                    else if (nums[i] + nums[left] + nums[right] < 0)
                        left++;
                    else
                    {
                        result.Add(new List<int>() { nums[i], nums[left], nums[right] });
                        //去重逻辑应该放在找到第一个三元组之后
                        while (right > left && nums[right] == nums[right - 1])
                            right--;
                        while (right > left && nums[left] == nums[left + 1])
                            left++;
                        //找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }
            }
            return result;
        }



    }
}
